Search Results

Documents authored by Panigrahi, Debmalya

Document
DOI: 10.4230/DagRep.13.10.76
Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422)

Authors: Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak

Published in: Dagstuhl Reports, Volume 13, Issue 10 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23422 "Graph Algorithms: Cuts, Flows, and Network Design". This seminar brought 25 leading researchers in graph algorithms together for a discussion of the recent progress and challenges in two areas: the design of fast algorithm for fundamental flow/cut problems and the design of approximation algorithms for basic network design problems. The seminar included several talks of varying lengths, a panel discussion, and an open problem session. In addition, sufficient time was set aside for research discussions and collaborations.
Cite as

Jason Li, Debmalya Panigrahi, Laura Sanita, and Thatchaphol Saranurak. Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422). In Dagstuhl Reports, Volume 13, Issue 10, pp. 76-89, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{li_et_al:DagRep.13.10.76,
  author =	{Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol},
  title =	{{Graph Algorithms: Cuts, Flows, and Network Design (Dagstuhl Seminar 23422)}},
  pages =	{76--89},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{10},
  editor =	{Li, Jason and Panigrahi, Debmalya and Sanita, Laura and Saranurak, Thatchaphol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.10.76},
  URN =		{urn:nbn:de:0030-drops-198357},
  doi =		{10.4230/DagRep.13.10.76},
  annote =	{Keywords: approximation, graph algorithm, maximum flow, minimum cut, network design}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.12
Efficient Algorithms and Hardness Results for the Weighted k-Server Problem

Authors: Anupam Gupta, Amit Kumar, and Debmalya Panigrahi

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
In this paper, we study the weighted k-server problem on the uniform metric in both the offline and online settings. We start with the offline setting. In contrast to the (unweighted) k-server problem which has a polynomial-time solution using min-cost flows, there are strong computational lower bounds for the weighted k-server problem, even on the uniform metric. Specifically, we show that assuming the unique games conjecture, there are no polynomial-time algorithms with a sub-polynomial approximation factor, even if we use c-resource augmentation for c < 2. Furthermore, if we consider the natural LP relaxation of the problem, then obtaining a bounded integrality gap requires us to use at least 𝓁 resource augmentation, where 𝓁 is the number of distinct server weights. We complement these results by obtaining a constant-approximation algorithm via LP rounding, with a resource augmentation of (2+ε)𝓁 for any constant ε > 0. In the online setting, an exp(k) lower bound is known for the competitive ratio of any randomized algorithm for the weighted k-server problem on the uniform metric. In contrast, we show that 2𝓁-resource augmentation can bring the competitive ratio down by an exponential factor to only O(𝓁² log 𝓁). Our online algorithm uses the two-stage approach of first obtaining a fractional solution using the online primal-dual framework, and then rounding it online.
Cite as

Anupam Gupta, Amit Kumar, and Debmalya Panigrahi. Efficient Algorithms and Hardness Results for the Weighted k-Server Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.APPROX/RANDOM.2023.12,
  author =	{Gupta, Anupam and Kumar, Amit and Panigrahi, Debmalya},
  title =	{{Efficient Algorithms and Hardness Results for the Weighted k-Server Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.12},
  URN =		{urn:nbn:de:0030-drops-188375},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.12},
  annote =	{Keywords: Online Algorithms, Weighted k-server, Integrality Gap, Hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.43
A General Framework for Learning-Augmented Online Allocation

Authors: Ilan Reuven Cohen and Debmalya Panigrahi

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Online allocation is a broad class of problems where items arriving online have to be allocated to agents who have a fixed utility/cost for each assigned item so to maximize/minimize some objective. This framework captures a broad range of fundamental problems such as the Santa Claus problem (maximizing minimum utility), Nash welfare maximization (maximizing geometric mean of utilities), makespan minimization (minimizing maximum cost), minimization of 𝓁_p-norms, and so on. We focus on divisible items (i.e., fractional allocations) in this paper. Even for divisible items, these problems are characterized by strong super-constant lower bounds in the classical worst-case online model. In this paper, we study online allocations in the learning-augmented setting, i.e., where the algorithm has access to some additional (machine-learned) information about the problem instance. We introduce a general algorithmic framework for learning-augmented online allocation that produces nearly optimal solutions for this broad range of maximization and minimization objectives using only a single learned parameter for every agent. As corollaries of our general framework, we improve prior results of Lattanzi et al. (SODA 2020) and Li and Xian (ICML 2021) for learning-augmented makespan minimization, and obtain the first learning-augmented nearly-optimal algorithms for the other objectives such as Santa Claus, Nash welfare, 𝓁_p-minimization, etc. We also give tight bounds on the resilience of our algorithms to errors in the learned parameters, and study the learnability of these parameters.
Cite as

Ilan Reuven Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2023.43,
  author =	{Cohen, Ilan Reuven and Panigrahi, Debmalya},
  title =	{{A General Framework for Learning-Augmented Online Allocation}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{43:1--43:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.43},
  URN =		{urn:nbn:de:0030-drops-180952},
  doi =		{10.4230/LIPIcs.ICALP.2023.43},
  annote =	{Keywords: Algorithms with predictions, Scheduling algorithms, Online algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.23
Online Paging with Heterogeneous Cache Slots

Authors: Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, and Neal E. Young

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
It is natural to generalize the online k-Server problem by allowing each request to specify not only a point p, but also a subset S of servers that may serve it. To initiate a systematic study of this generalization, we focus on uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a page p, but also a subset S of cache slots, and is satisfied by having a copy of p in some slot in S. We call this problem Slot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family 𝒮 ⊆ 2^[k] of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache size k and family 𝒮. If all request sets are allowed (𝒮 = 2^[k]), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging (𝒮 = {[k]}). As a function of |𝒮| and k, the optimal deterministic ratio is polynomial: at most O(k²|𝒮|) and at least Ω(√{|𝒮|}). For any laminar family {𝒮} of height h, the optimal ratios are O(hk) (deterministic) and O(h²log k) (randomized). The special case that we call All-or-One Paging extends standard Paging by allowing each request to specify a specific slot to put the requested page in. For All-or-One Paging the optimal competitive ratios are Θ(k) (deterministic) and Θ(log k) (randomized), while the offline problem is NP-hard. We extend the deterministic upper bound to the weighted variant of All-or-One Paging (a generalization of standard Weighted Paging), showing that it is also Θ(k). Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set P of pages, and is satisfied by fetching any page from P into the cache. The optimal ratios for the latter problem (with laminar family of height h) are at most hk (deterministic) and hH_k (randomized).
Cite as

Marek Chrobak, Samuel Haney, Mehraneh Liaee, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, and Neal E. Young. Online Paging with Heterogeneous Cache Slots. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chrobak_et_al:LIPIcs.STACS.2023.23,
  author =	{Chrobak, Marek and Haney, Samuel and Liaee, Mehraneh and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi and Young, Neal E.},
  title =	{{Online Paging with Heterogeneous Cache Slots}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.23},
  URN =		{urn:nbn:de:0030-drops-176759},
  doi =		{10.4230/LIPIcs.STACS.2023.23},
  annote =	{Keywords: Caching and paging algorithms, k-server, weighted paging, laminar family}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.45
Sparsification of Directed Graphs via Cut Balance

Authors: Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In this paper, we consider the problem of designing cut sparsifiers and sketches for directed graphs. To bypass known lower bounds, we allow the sparsifier/sketch to depend on the balance of the input graph, which smoothly interpolates between undirected and directed graphs. We give nearly matching upper and lower bounds for both for-all (cf. Benczúr and Karger, STOC 1996) and for-each (Andoni et al., ITCS 2016) cut sparsifiers/sketches as a function of cut balance, defined the maximum ratio of the cut value in the two directions of a directed graph (Ene et al., STOC 2016). We also show an interesting application of digraph sparsification via cut balance by using it to give a very short proof of a celebrated maximum flow result of Karger and Levine (STOC 2002).
Cite as

Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of Directed Graphs via Cut Balance. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cen_et_al:LIPIcs.ICALP.2021.45,
  author =	{Cen, Ruoxu and Cheng, Yu and Panigrahi, Debmalya and Sun, Kevin},
  title =	{{Sparsification of Directed Graphs via Cut Balance}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{45:1--45:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.45},
  URN =		{urn:nbn:de:0030-drops-141143},
  doi =		{10.4230/LIPIcs.ICALP.2021.45},
  annote =	{Keywords: Graph sparsification, directed graphs, cut sketches, space complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.70
Universal Algorithms for Clustering Problems

Authors: Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This paper presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers such that they are a good solution for any subset of clients that actually realize. Specifically, we aim for low regret, defined as the maximum over all subsets of the difference between the cost of the algorithm’s solution and that of an optimal solution. A universal algorithm’s solution sol for a clustering problem is said to be an (α, β)-approximation if for all subsets of clients C', it satisfies sol(C') ≤ α ⋅ opt(C') + β ⋅ mr, where opt(C') is the cost of the optimal solution for clients C' and mr is the minimum regret achievable by any solution. Our main results are universal algorithms for the standard clustering objectives of k-median, k-means, and k-center that achieve (O(1), O(1))-approximations. These results are obtained via a novel framework for universal algorithms using linear programming (LP) relaxations. These results generalize to other 𝓁_p-objectives and the setting where some subset of the clients are fixed. We also give hardness results showing that (α, β)-approximation is NP-hard if α or β is at most a certain constant, even for the widely studied special case of Euclidean metric spaces. This shows that in some sense, (O(1), O(1))-approximation is the strongest type of guarantee obtainable for universal clustering.
Cite as

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Universal Algorithms for Clustering Problems. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 70:1-70:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ICALP.2021.70,
  author =	{Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
  title =	{{Universal Algorithms for Clustering Problems}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{70:1--70:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.70},
  URN =		{urn:nbn:de:0030-drops-141397},
  doi =		{10.4230/LIPIcs.ICALP.2021.70},
  annote =	{Keywords: universal algorithms, clustering, k-median, k-means, k-center}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.34
Online Two-Dimensional Load Balancing

Authors: Ilan Cohen, Sungjin Im, and Debmalya Panigrahi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we consider the problem of assigning 2-dimensional vector jobs to identical machines online so to minimize the maximum load on any dimension of any machine. For arbitrary number of dimensions d, this problem is known as vector scheduling, and recent research has established the optimal competitive ratio as O((log d)/(log log d)) (Im et al. FOCS 2015, Azar et al. SODA 2018). But, these results do not shed light on the situation for small number of dimensions, particularly for d = 2 which is of practical interest. In this case, a trivial analysis shows that the classic list scheduling greedy algorithm has a competitive ratio of 3. We show the following improvements over this baseline in this paper: - We give an improved, and tight, analysis of the list scheduling algorithm establishing a competitive ratio of 8/3 for two dimensions. - If the value of opt is known, we improve the competitive ratio to 9/4 using a variant of the classic best fit algorithm for two dimensions. - For any fixed number of dimensions, we design an algorithm that is provably the best possible against a fractional optimum solution. This algorithm provides a proof of concept that we can simulate the optimal algorithm online up to the integrality gap of the natural LP relaxation of the problem.
Cite as

Ilan Cohen, Sungjin Im, and Debmalya Panigrahi. Online Two-Dimensional Load Balancing. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2020.34,
  author =	{Cohen, Ilan and Im, Sungjin and Panigrahi, Debmalya},
  title =	{{Online Two-Dimensional Load Balancing}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.34},
  URN =		{urn:nbn:de:0030-drops-124415},
  doi =		{10.4230/LIPIcs.ICALP.2020.34},
  annote =	{Keywords: Online algorithms, scheduling, multi-dimensional}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.54
Robust Algorithms for TSP and Steiner Tree

Authors: Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.
Cite as

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Robust Algorithms for TSP and Steiner Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ICALP.2020.54,
  author =	{Ganesh, Arun and Maggs, Bruce M. and Panigrahi, Debmalya},
  title =	{{Robust Algorithms for TSP and Steiner Tree}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.54},
  URN =		{urn:nbn:de:0030-drops-124619},
  doi =		{10.4230/LIPIcs.ICALP.2020.54},
  annote =	{Keywords: Robust optimization, Steiner tree, traveling salesman problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.69
Online Algorithms for Weighted Paging with Predictions

Authors: Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we initiate the study of the weighted paging problem with predictions. This continues the recent line of work in online algorithms with predictions, particularly that of Lykouris and Vassilvitski (ICML 2018) and Rohatgi (SODA 2020) on unweighted paging with predictions. We show that unlike unweighted paging, neither a fixed lookahead nor knowledge of the next request for every page is sufficient information for an algorithm to overcome existing lower bounds in weighted paging. However, a combination of the two, which we call the strong per request prediction (SPRP) model, suffices to give a 2-competitive algorithm. We also explore the question of gracefully degrading algorithms with increasing prediction error, and give both upper and lower bounds for a set of natural measures of prediction error.
Cite as

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online Algorithms for Weighted Paging with Predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 69:1-69:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jiang_et_al:LIPIcs.ICALP.2020.69,
  author =	{Jiang, Zhihao and Panigrahi, Debmalya and Sun, Kevin},
  title =	{{Online Algorithms for Weighted Paging with Predictions}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{69:1--69:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.69},
  URN =		{urn:nbn:de:0030-drops-124761},
  doi =		{10.4230/LIPIcs.ICALP.2020.69},
  annote =	{Keywords: Online algorithms, paging}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.70
Retracting Graphs to Cycles

Authors: Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We initiate the algorithmic study of retracting a graph into a cycle in the graph, which seeks a mapping of the graph vertices to the cycle vertices so as to minimize the maximum stretch of any edge, subject to the constraint that the restriction of the mapping to the cycle is the identity map. This problem has its roots in the rich theory of retraction of topological spaces, and has strong ties to well-studied metric embedding problems such as minimum bandwidth and 0-extension. Our first result is an O(min{k, sqrt{n}})-approximation for retracting any graph on n nodes to a cycle with k nodes. We also show a surprising connection to Sperner’s Lemma that rules out the possibility of improving this result using certain natural convex relaxations of the problem. Nevertheless, if the problem is restricted to planar graphs, we show that we can overcome these integrality gaps by giving an optimal combinatorial algorithm, which is the technical centerpiece of the paper. Building on our planar graph algorithm, we also obtain a constant-factor approximation algorithm for retraction of points in the Euclidean plane to a uniform cycle.
Cite as

Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Retracting Graphs to Cycles. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 70:1-70:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{haney_et_al:LIPIcs.ICALP.2019.70,
  author =	{Haney, Samuel and Liaee, Mehraneh and Maggs, Bruce M. and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi},
  title =	{{Retracting Graphs to Cycles}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{70:1--70:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.70},
  URN =		{urn:nbn:de:0030-drops-106462},
  doi =		{10.4230/LIPIcs.ICALP.2019.70},
  annote =	{Keywords: Graph algorithms, Graph embedding, Planar graphs, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.43
Profit Sharing and Efficiency in Utility Games

Authors: Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, and Venetia Pliatsika

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study utility games (Vetta, FOCS 2002) where a set of players join teams to produce social utility, and receive individual utility in the form of payments in return. These games have many natural applications in competitive settings such as labor markets, crowdsourcing, etc. The efficiency of such a game depends on the profit sharing mechanism - the rule that maps utility produced by the players to their individual payments. We study three natural and widely used profit sharing mechanisms - egalitarian or equal sharing, marginal gain or value addition when a player joins, and marginal loss or value depletion when a player leaves. For these settings, we give tight bounds on the price of anarchy, thereby allowing comparison between these popular mechanisms from a (worst case) social welfare perspective.
Cite as

Sreenivas Gollapudi, Kostas Kollias, Debmalya Panigrahi, and Venetia Pliatsika. Profit Sharing and Efficiency in Utility Games. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gollapudi_et_al:LIPIcs.ESA.2017.43,
  author =	{Gollapudi, Sreenivas and Kollias, Kostas and Panigrahi, Debmalya and Pliatsika, Venetia},
  title =	{{Profit Sharing and Efficiency in Utility Games}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{43:1--43:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.43},
  URN =		{urn:nbn:de:0030-drops-78329},
  doi =		{10.4230/LIPIcs.ESA.2017.43},
  annote =	{Keywords: Price of anarchy, submodular maximization, coverage functions}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.9
Symmetric Interdiction for Matching Problems

Authors: Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates optimization to symmetric interdiction for a broad class of optimization problems. We then study the symmetric matching interdiction problem - with applications in traffic engineering - in more detail. This problem can be simply stated as follows: find a matching whose removal minimizes the size of the maximum matching in the remaining graph. We show that this problem is APX-hard, and obtain a 3/2-approximation algorithm that improves on the approximation guarantee provided by the general framework.
Cite as

Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, and Ravi Sundaram. Symmetric Interdiction for Matching Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{haney_et_al:LIPIcs.APPROX-RANDOM.2017.9,
  author =	{Haney, Samuel and Maggs, Bruce and Maiti, Biswaroop and Panigrahi, Debmalya and Rajaraman, Rajmohan and Sundaram, Ravi},
  title =	{{Symmetric Interdiction for Matching Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.9},
  URN =		{urn:nbn:de:0030-drops-75587},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.9},
  annote =	{Keywords: Approximation algorithms, matching, interdiction Digital Object}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.7
Faster Algorithms for the Geometric Transportation Problem

Authors: Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.
Cite as

Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster Algorithms for the Geometric Transportation Problem. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2017.7,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Panigrahi, Debmalya and Varadarajan, Kasturi R. and Xiao, Allen},
  title =	{{Faster Algorithms for the Geometric Transportation Problem}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.7},
  URN =		{urn:nbn:de:0030-drops-72344},
  doi =		{10.4230/LIPIcs.SoCG.2017.7},
  annote =	{Keywords: transportation map, earth mover's distance, shape matching, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.64
Online Set Cover with Set Requests

Authors: Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We consider a generic online allocation problem that generalizes the classical online set cover framework by considering requests comprising a set of elements rather than a single element. This problem has multiple applications in cloud computing, crowd sourcing, facility planning, etc. Formally, it is an online covering problem where each online step comprises an offline covering problem. In addition, the covering sets are capacitated, leading to packing constraints. We give a randomized algorithm for this problem that has a nearly tight competitive ratio in both objectives: overall cost and maximum capacity violation. Our main technical tool is an online algorithm for packing/covering LPs with nested constraints, which may be of interest in other applications as well.
Cite as

Kshipra Bhawalkar, Sreenivas Gollapudi, and Debmalya Panigrahi. Online Set Cover with Set Requests. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 64-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bhawalkar_et_al:LIPIcs.APPROX-RANDOM.2014.64,
  author =	{Bhawalkar, Kshipra and Gollapudi, Sreenivas and Panigrahi, Debmalya},
  title =	{{Online Set Cover with Set Requests}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{64--79},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.64},
  URN =		{urn:nbn:de:0030-drops-46883},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.64},
  annote =	{Keywords: Online Algorithms, Set Cover}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.300
The Semi-stochastic Ski-rental Problem

Authors: Aleksander Madry and Debmalya Panigrahi

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract
In this paper, we introduce the semi-stochastic model for dealing with input uncertainty in optimization problems. This model is a hybrid between the overly pessimistic online model and the highly optimistic stochastic (or Bayesian) model. In this model, the algorithm can obtain only limited stochastic information about the future (i.e. about the input distribution)---as the amount of stochastic information we make available to the algorithm grows from no information to full information, we interpolate between the online and stochastic models. The central question in this framework is the trade-off between the performance of an algorithm, and the stochastic information that it can access. As a first step towards understanding this trade-off, we consider the ski-rental problem in the semi-stochastic setting. More precisely, given a desired competitive ratio, we give upper and lower bounds on the amount of stochastic information required by a deterministic algorithm for the ski-rental problem to achieve that competitive ratio.
Cite as

Aleksander Madry and Debmalya Panigrahi. The Semi-stochastic Ski-rental Problem. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 300-311, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{madry_et_al:LIPIcs.FSTTCS.2011.300,
  author =	{Madry, Aleksander and Panigrahi, Debmalya},
  title =	{{The Semi-stochastic Ski-rental Problem}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{300--311},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.300},
  URN =		{urn:nbn:de:0030-drops-33305},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.300},
  annote =	{Keywords: online optimization, stochastic algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact